package com.sx.sx1.lintcode.day717;
import java.util.*;

public class LC194 {

    static class Solution {
        /**
         * @param str: the string
         * @param dict: the dictionary
         * @return: return words which  are subsequences of the string
         */
        public List<String> findWords(String str, List<String> dict) {
            List<String> ans = new ArrayList<>();
            Map<Character,List<Integer>> pos= new HashMap<>();
            for (int i = 0; i <str.length() ; i++) {
                char c = str.charAt(i);
                if(!pos.containsKey(c)){
                    pos.put(c,new ArrayList<>());
                }

                pos.get(c).add(i);
            }


            for (String s : dict) {
                if(pos.containsKey(s.charAt(0))){
                    List<Integer> idxs = pos.get(s.charAt(0));
                    for (int idx : idxs) {
                        if(issubstring(str,idx,s)){
                            ans.add(s);
                            break;
                        }
                    }
                }
            }
            return ans;
        }

        //判断s1[start...] 中包含的子序列中是否有s2这一种
        public boolean issubstring(String s1,int start,String s2){
            int left =start;
            int right = 0;
            int  n= s1.length();
            int n2 = s2.length();

            if(n-start < n2) return false;

            while (left<n){
                if(s1.charAt(left) == s2.charAt(right)){
                    right++;
                }

                left++;

                if(right == n2) return true;
            }

            return false;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        String str1="bcogtadsjofisdhklasdj";
        String[] dict1={"book","code","tag"};


        String str2="nmownhiterer";
        String[] dict2={"nowhere","monitor","moniter"};

        System.out.println(obj.findWords(str1,new ArrayList<>(Arrays.asList("book","code","tag"))));
        System.out.println(obj.findWords(str2,new ArrayList<>(Arrays.asList("nowhere","monitor","moniter"))));
    }


    /*
    输入数据
"xpmzbmlbxeirzveewcmzbciehankbqfxhvzpwsrhfowvaikyvu"
["xbpwsrhf","rt","byq","ae","xpmzbmlveebciefxhvzpwfoyvu","aft","k","liiurfqu","exg","qfxvzpw"]
输出数据
["xbpwsrhf","xbpwsrhf","xpmzbmlveebciefxhvzpwfoyvu","k","k","qfxvzpw"]
期望答案
["xbpwsrhf","xpmzbmlveebciefxhvzpwfoyvu","k","qfxvzpw"]
     */

    static class SolutionOK {
        /**
         * @param str: the string
         * @param dict: the dictionary
         * @return: return words which  are subsequences of the string
         */
        public List<String> findWords(String str, List<String> dict) {
            char[] str1 = str.toCharArray();
            int n = str.length();

            Map<Character, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (!map.containsKey(str1[i])) map.put(str1[i], new ArrayList<>());
                map.get(str1[i]).add(i);
            }

            List<String> ans = new ArrayList<>();
            for (int i = 0; i < dict.size(); i++) {
                String s1 = dict.get(i);
                char[] str2 = s1.toCharArray();

                if (map.containsKey(str2[0])) {
                    List<Integer> indexs = map.get(str2[0]);
                    for (Integer index : indexs) {
                        if (isSeq(str1, str2, index)) {
                            ans.add(s1);
                            break;
                        }
                    }
                }
            }

            return ans;

        }

        //判断str2是否是str1的子序列
        public static boolean isSeq(char[] str1, char[] str2, int L) {
            int n = str1.length;
            int m = str2.length;
            int R = 0;
            while (L < n && R < m) {
                if (str1[L] == str2[R]) {
                    R++;
                }
                L++;
            }
            return R == m;
        }

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
194 · 寻找单词
算法
中等
通过率
73%

题目
题解34
笔记
讨论40
排名
记录
描述
给定一个字符串str，和一个字典dict，你需要找出字典里的哪些单词是字符串的子序列，返回这些单词。返回单词的顺序应与词典中的顺序相同。

|str|<=1000
2.字典中所有单词长度的总和<=1000
(题目保证所有字母均为小写)

样例
例1:

输入:
str="bcogtadsjofisdhklasdj"
dict=["book","code","tag"]
输出:
["book"]
解释:只有book是str的子序列
例2:

输入:
str="nmownhiterer"
dict=["nowhere","monitor","moniter"]
输出:
["nowhere","moniter"]
挑战
|str|<=100000

标签
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
1670/1859
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
